#include <stdio.h>
#include <stdlib.h>

struct Point {
  double x,y,z;
};

struct Diagonal {
  struct Point first,second;
};

enum bool { false,true };
enum VertexType { CONVEX, NOCONVEX };
enum PointLineRelation{  LEFT,  RIGHT,  BEYOND,  BEHIND, BETWEEN, ORIGIN, DESTINATION  };

double min(double a,double b) {
  return a > b ? b:a;
}

double max(double a,double b) {
  return a < b ? b:a;
}

struct Point *PointWithMinX(struct Point *a,struct Point *b) {
  return a->x > b->x ? b:a;
}

struct Point *PointWithMaxX(struct Point *a,struct Point *b) {
  return a->x > b->x ? a:b;
}

struct Point *PointWithMinY(struct Point *a,struct Point *b) {
  return a->y > b->y ? b:a;
}

struct Point *PointWithMaxY(struct Point *a,struct Point *b) {
  return a->y > b->y ? a:b;
}

//Z cordinate is supposed to be constant
//If diagonals intersects in the edges result is false
enum bool ArePlaneDiagonalsIntersected(struct Diagonal *a,struct Diagonal *b) {
  double xdiff1,xdiff2,ydiff1,ydiff2;
  
  ydiff1 = PointWithMinX(&a->first,&a->second)->y - PointWithMinX(&b->first,&b->second)->y;
  ydiff2 = PointWithMaxX(&a->first,&a->second)->y - PointWithMaxX(&b->first,&b->second)->y;
  if (ydiff1*ydiff2 >= 0) {
    return false;
  } else {
    xdiff1 = PointWithMinY(&a->first,&a->second)->x - PointWithMinY(&b->first,&b->second)->x;
    xdiff2 = PointWithMaxY(&a->first,&a->second)->x - PointWithMaxY(&b->first,&b->second)->x;
    if(xdiff1*xdiff2 >= 0) return false;
      else return true;
    }
}

int SignOfPlaneABxBC(struct Point *A,struct Point *B,struct Point *C) {
  if ((B->x-A->x)*(C->y-B->y)-(B->y-A->y)*(C->x-B->x) > 0) return 1;
    else if((B->x-A->x)*(C->y-B->y)-(B->y-A->y)*(C->x-B->x) < 0) return -1;
      else return 0;
}

//ABxBC is supposed to be >0 or <0
enum VertexType DefineVertexType(struct Point *polygon, int vertex_number) {
  if (SignOfPlaneABxBC(&polygon[vertex_number-1],&polygon[vertex_number],
        &polygon[vertex_number+1]) == 1) return CONVEX;
  else return NOCONVEX;
}

double SquaredPlaneVectorLength(struct Point *start,struct Point *destination) {
  return (destination->x-start->x)*(destination->x-start->x) + 
          (destination->y-start->y)*(destination->y-start->y);
}

enum bool ArePointsEqual(struct Point *a,struct Point *b) {
  if(a->x == b->x && a->y == b->y) return true;
    else return false;
}

enum PointLineRelation DefinePointLineRelation(struct Point *start,
                                               struct Point *destination,
                                               struct Point *CheckedPoint) {
  int sign = SignOfPlaneABxBC(CheckedPoint,start,destination);
  if (sign == 1) {
    return LEFT;
  } else if(sign == -1) {
    return RIGHT;
  } else {
    if(((destination->x-start->x)*(CheckedPoint->x-start->x) < 0) ||
       ((destination->y-start->y)*(CheckedPoint->y-start->y) < 0))
        return BEHIND;
    else if (SquaredPlaneVectorLength(start,destination) <
             SquaredPlaneVectorLength(start,CheckedPoint))
      return BEYOND;
    else if (ArePointsEqual(start,CheckedPoint) == 1) return ORIGIN;
    else if (ArePointsEqual(destination,CheckedPoint) == 1) return DESTINATION;
    else return BETWEEN;
  }
}

int PointWithMaxXInArray(struct Point *set,int numof_points) {
  int i,max; 

  max = 0;
  for(i=1;i<numof_points;++i) {
    if(set[i].x > set[max].x) max = i;
  }
  return max;
}

//If point belongs to edge function returns true
enum bool DoesPointBelongToPolygon(struct Point *polygon, int numof_vertexes, 
                                   struct Point *A) {
  int i,parity;
  enum PointLineRelation temp_relation1,temp_relation2;
  struct Point temp_destination;
  temp_destination.x = polygon[PointWithMaxXInArray(polygon,numof_vertexes)].x;
  temp_destination.y = A->y;
  temp_destination.z = A->z;
  
  parity = 0;
  temp_relation1 = DefinePointLineRelation(A,&temp_destination,&polygon[0]);
  if ((temp_relation1 != LEFT) && (temp_relation1 != RIGHT)) {
    if(DefineVertexType(polygon,0) == CONVEX) parity = 1 - parity;
  }
  for(i=1;i<numof_vertexes;++i) {
    temp_relation2 = DefinePointLineRelation(A,&temp_destination,&polygon[i]);
    //LEFT == 0 RIGHT == 1 => look behind 
    if ((temp_relation1 == LEFT && temp_relation2 == LEFT) ||
        (temp_relation1 == RIGHT && temp_relation2 == RIGHT)) {
      temp_relation1 = temp_relation2;
      continue;
    } else if(temp_relation1+temp_relation2 == 1) parity = 1-parity;
    else if (temp_relation2 != LEFT && temp_relation2 != RIGHT) {
      if(DefineVertexType(polygon,i) == CONVEX) parity = 1-parity;
    else if (temp_relation2 == ORIGIN || temp_relation2 == DESTINATION)
      return true;
    temp_relation1 = temp_relation2;
    }
  }
  return parity;
}
  

enum bool DoesDiagBelongToPolygon(struct Point *polygon, int numof_vertexes,  
                                  struct Diagonal *a) {
  int i,sign;
  struct Diagonal temp;
  
  for(i=1;i<numof_vertexes;++i) {
    temp.first = polygon[i-1];
    temp.second = polygon[i];
    if(ArePlaneDiagonalsIntersected(&temp,a) == true) 
      return false;
  }
}

int main() {
  struct Point *polygon,A;
  polygon = (struct Point *)malloc(3*sizeof(struct Point));
  polygon[0].x = 0.0;
  polygon[0].y = 0.0;
  polygon[0].z = 0.0;
  polygon[1].x = 1.0;
  polygon[1].y = 0.0;
  polygon[1].z = 0.0;
  polygon[2].x = -1.0;
  polygon[2].y = 1.0;
  polygon[2].z = 0.0;
  A.x = -0.1;
  A.y = 0.1;
  A.z = 0.0;
  
  printf("%d\n",DoesPointBelongToPolygon(polygon,3,&A));
  return 0;
}
